#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeLinkNode
{
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

//二叉树的下一个结点，考虑到，是否空，是否有右孩子，是否有父节点，是父节点的哪个孩子
TreeLinkNode *GetNext(TreeLinkNode *pNode)
{
    if (!pNode)
    {
        return nullptr;
    }

    if (pNode->right) //有右孩子节点
    {
        pNode = pNode->right; //往右一次
        while (pNode->left)
        {
            pNode = pNode->left; //往左走到头
        }
        return pNode;
    }

    while (pNode->next) //有父节点
    {
        if (pNode->next->left == pNode) //当前节点是其父节点的左孩子
        {
            return pNode->next;
        }
        pNode = pNode->next;
    }
    
    return nullptr; //所给pNode为中序遍历的最后一个
}

void test()
{
}

int main()
{
    test();
    return 0;
}